//
//  BinaryTree.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/9.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

/// 真二叉树：每个节点的出度都是偶数(0或者2)
public class BinaryTree<Element> {
    
    public typealias Node = BinaryTreeNode
    
    /// 规模
    var _size: Int
    /// 根节点
    var _root: Node<Element>?
   
    public var root: Node<Element>? { return _root }
    public var count: Int { return _size }
    public var isEmpty: Bool {
        precondition(_size == 0)
        return root == nil
    }
    
    public init() { _size = 0 }

    
    public init(_ rootValue: Element) {
        _size = 1
        _root = Node(rootValue)
    }
}

// MARK: override point
extension BinaryTree {
    
    /// 更新节点nd的高度
    @discardableResult
    internal func updateHeight(_ nd: Node<Element>) -> Int {
        // 常规二叉树规则
        // 节点nd的高度 = nd的左孩子和右孩子中高度最大者+1
        // 这里要求左右孩子的高度是确定的
        nd.height = max(stature(nd.lchild), stature(nd.rchild)) + 1
        return nd.height
    }
    
    /// 更新节点nd及祖先的高度
    internal func updateHeightAbove(_ nd: Node<Element>?) {
        var nd = nd
        while nd != nil {
            updateHeight(nd!)
            nd = nd?.parent
        }
    }
}
